#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 判断二叉树是否为完全二叉树的函数
int isCompleteBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return 1;
    }
    // 创建一个模拟队列，用于层次遍历
    TreeNode** queue = (TreeNode**)malloc(sizeof(TreeNode*) * 1000);  // 简单分配一定初始空间，可优化为动态扩容
    int front = 0, rear = 0;
    // 将根节点入队
    queue[rear++] = root;
    int flag = 0;  // 标记是否已经遇到过叶节点或者只有左子树的节点
    while (front < rear) {
        TreeNode* node = queue[front++];
        // 获取当前节点的左右子节点
        TreeNode* left = node->left;
        TreeNode* right = node->right;
        // 如果已经遇到过叶节点或者只有左子树的节点，当前节点不应再有子节点
        if (flag && (left!= NULL || right!= NULL)) {
            free(queue);
            return 0;
        }
        if (left == NULL && right!= NULL) {
            free(queue);
            return 0;
        }
        if (left!= NULL) {
            queue[rear++] = left;
        }
        if (right!= NULL) {
            queue[rear++] = right;
        }
        // 如果当前节点左子树为空或者右子树为空，标记已遇到叶节点或只有左子树的节点情况
        if (left == NULL || right == NULL) {
            flag = 1;
        }
    }
    free(queue);
    return 1;
}